package com.liang.leetcode.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * 70.爬楼梯
 */
public class Dp02_ClimbStairs {
    public static void main(String[] args) {
        int n = 50;
        System.out.println(climbStairs32(n));
    }

    /**
     * 解法1：递归，会超时
     */
    public static int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    /**
     * 解法2：记忆化搜索
     * 减少重复计算，自顶向下的解法
     */
    static Map<Integer, Integer> tempMap = new HashMap();

    public static int climbStairs2(int n) {
        // 确定边界条件
        if (n == 1) return 1;
        if (n == 2) return 2;
        // 递归
        if (!tempMap.containsKey(n)) {
            // 备忘录没有，执行递归计算，并且把结果保存到备忘录map中
            tempMap.put(n, (climbStairs2(n - 1) + climbStairs2(n - 2)));
        }
        return tempMap.get(n);
    }

    /**
     * 解法3：动态规划，自底向上
     * 爬到 n 阶楼梯，可以从第 n-1 阶爬 1 阶上来，或者从第 n-2 阶爬 2 阶上来
     * 状态转移方程：f(n) = f(n-1) + f(n-2)
     */
    // 常规方式
    public int climbStairs31(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 解法3 优化：用变量记录代替数组
     */
    public static int climbStairs32(int n) {
        // 确定边界值
        if (n <= 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        // 爬到第1阶、第2阶楼梯方法数
        int a = 1, b = 2;
        // 从第3阶开始，只有两种上楼方式，从前一层爬一楼和从前二层爬两楼
        int temp = 0;       // 用 temp 存储爬到当前阶的方法数
        for (int i = 3; i <= n; i++) {
            temp = a + b;   // 计算爬到当前阶的方法数
            a = b;          // 更新a为上一阶的方法数（即原来的b） n
            b = temp;       // 更新b为当前阶的方法数（即新的temp）n-1
        }
        return temp;
    }

}
